package com.cty.C_SortAlgorithms.F_QuickSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/18 11:14
 * @Description: 快速排序  手动排序 + 右端做枢纽 + 划分
 * @version: 1.0
 */
public class QuickSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public QuickSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组尾部插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    /**
     * 交换
     * @param a
     * @param b
     */
    private void swap(int a, int b){
        DataItem temp = array[a].getItem();
        array[a].setItem(array[b]);
        array[b].setItem(temp);
    }

    /**
     * 划分
     * @param left
     * @param right
     * @param pivot
     * @return
     */
    private int partition(int left, int right, long pivot){
        int leftPtr = left - 1;
        int rightPtr = right;

        while(true){
            while(array[++leftPtr].getKey() < pivot);  // 从左端开始，查找 关键字>=pivot 的数据项
            while(rightPtr>left && array[--rightPtr].getKey() > pivot);  // 从右端开始，查找 关键字<=pivot 的数据项
            // 注意左边界越界检查

            if(leftPtr >= rightPtr)
                break;  // 指针交叉，划分结束
            else
                swap(leftPtr, rightPtr);
        }  // end while(true)

        swap(right, leftPtr);  // 将枢纽移到中间
        return leftPtr;  // 返回枢纽索引位置
    }  // end partition{}

    /**
     * 递归实现快速排序
     * @param left
     * @param right
     */
    private void recQuickSort(int left, int right){
        if(right <= left)
            return;
        else{
            // 划分
            long pivot = array[right].getKey();  // 直接选择最右端值作为枢纽，但在数据偏逆序分布情况下效率极低；另外注意在划分中要检查左端是否越界
            int pivotIndex = partition(left, right, pivot);
            // 递归划分
            recQuickSort(left, pivotIndex-1);
            recQuickSort(pivotIndex+1, right);
        }  // end else
    }  // end recQuickSort()

    /**
     * 快速排序
     *      平均时间复杂度：  O(N*logN)    数据随机分布    每次划分近似于二分，共划分 logN + 1 次，每次划分约比较 N 次，交换小于 N/2 次
     *      最好情况：        O(N*logN)    数据随机分布
     *      最坏情况：        O(N^2)       数据有序分布    每次划分都相当于选择最值，共划分 N-1 次
     *      空间复杂度：      O(logN~N)    递归造成栈空间的使用
     *      排序方式：                     内部排序
     *      稳定性：                       不稳定
     */
    public void quickSort(){
        recQuickSort(0, nItems-1);
    }

}  // end QuickSort2{}
